def is_palindrome(node):
    def find_middle():
        i, j = node, node
        while j and j.next:
            i = i.next
            j = j.next.next
        return i

    def reverse(middle):
        pre, curr, nextnode = None, node, None
        while curr != middle:
            nextnode = curr.next
            curr.next = pre
            pre = curr
            curr = nextnode
        return pre

    def is_same(node1, node2):
        while node1 and node2:
            if node1.val != node2.val:
                return False
            node1 = node1.next
            node2 = node2.next
        return (node1 is None) and (node2 is None)

    middle = find_middle()
    reversed_half = reverse(middle)
    return is_same(reversed_half, middle) or is_same(reversed_half, middle.next)


from utils import list12321, print_list, list123321, list12345, list1

print_list(list1)
print(is_palindrome(list1))
